package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
 **/
public class No014_ii {

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：35.2 MB, 在所有 Java 提交中击败了58.61%的用户
     */
    public static int cuttingRope(int n) {
        if (n <= 3) return n - 1;

        long res = 1L;
        while (n > 4) {
            res = res * 3 % 1000000007;
            n -= 3;
        }

        return (int) (res * n % 1000000007);
    }
}
